package com.zj.leetcode.medium.dynamicProgramming;

/**
 * @program: algorithm
 * @description: 零钱兑换 II
 * 518 coin-change-2
 * @author: Zhang Bo
 * @create: 2022-05-13 14:25:26
 **/
public class CoinChange2 {
    public static void main(String[] args) {
        Solution solution = new CoinChange2().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * amount = 5, coins = [1, 2, 5]
         * <p>
         * 1  2  3  4  5
         * 1  1
         * 2
         * 5
         *
         * @param amount
         * @param coins
         * @return
         */
        public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 0; i < coins.length; i++) { // 遍历物品
                for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                    dp[j] += dp[j - coins[i]];
                }
            }
            return dp[amount];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
